package q160_getIntersectionNode;

import CommonClass.Common.ListNode;
public class Solution_2 {


    /**
     * 如果 a=b，则指针 pA 会遍历完链表 headA，指针 pB 会遍历完链表 headB，两个指针不会同时到达链表的尾节点，
     * 然后指针 pA 移到链表 headB 的头节点，指针 pB 移到链表 headA 的头节点，
     * 然后两个指针继续移动，在指针 pA 移动了 a+c+b 次、指针 pB 移动了 b+c+a 次之后，
     *  两个指针会同时到达两个链表相交的节点，该节点也是两个指针第一次同时指向的节点，此时返回相交的节点。
     *  如果不相交，那么经过m+n次后两者都变成null了
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            // 注意当A和B长度不相同时，pA和pB都会遍历完A和B后来到另一条链表，直到两者相遇或者同时变成空
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

}
